package basic.study.algorithms.solution.DynamicProgramming;

/**
 * @author Kevin
 * @date 2020/2/19 17:52
 * 计算莱文斯坦距离
 */
public class SearchEngine {
    //回溯算法
    /**
     * 回溯是一个递归处理的过程。如果 a[i]与 b[j]匹配，我们递归考察 a[i+1]和 b[j+1]。如果 a[i]与 b[j]不匹配，那我们有多种处理方式可选：
     * 可以删除 a[i]，然后递归考察 a[i+1]和 b[j]；
     * 可以删除 b[j]，然后递归考察 a[i]和 b[j+1]；
     * 可以在 a[i]前面添加一个跟 b[j]相同的字符，然后递归考察 a[i]和 b[j+1];
     * 可以在 b[j]前面添加一个跟 a[i]相同的字符，然后递归考察 a[i+1]和 b[j]；
     * 可以将 a[i]替换成 b[j]，或者将 b[j]替换成 a[i]，然后递归考察 a[i+1]和 b[j+1]。
     */
    private static char[] a = "mitcmu".toCharArray();
    private static char[] b = "mtacnu".toCharArray();
    private static int n = 6;
    private static int m = 6;
    private static int minDist = Integer.MAX_VALUE;//存储结果

    //调用方式 lwstBT(0, 0, 0);
    public static void lwstBT(int i, int j, int edist) {
        if (i == n || j == n) {
            if (i < n) edist += (n - i);
            if (j < m) edist += (m - j);
            if (edist < minDist) minDist = edist;
            return ;
        }
        if (a[i] == b[j]){//两个字符匹配
            lwstBT(i+1, j+1, edist);
        } else {//连个字符不匹配
            lwstBT(i + 1, j, edist + 1);// 删除a[i]或者b[j]前添加一个字符
            lwstBT(i, j + 1, edist + 1);// 删除b[j]或者a[i]前添加一个字符
            lwstBT(i + 1, j + 1, edist + 1);// 将a[i]和b[j]替换为相同字符
        }
    }
    public static void main(String[] args) {
        lwstBT(0, 0, 0);
        System.out.println(minDist);
    }
    /**
     *
     * 状态转移方程
     如果：a[i]!=b[j]，那么：min_edist(i, j)就等于：
     min(min_edist(i-1,j)+1, min_edist(i,j-1)+1, min_edist(i-1,j-1)+1)

     如果：a[i]==b[j]，那么：min_edist(i, j)就等于：
     min(min_edist(i-1,j)+1, min_edist(i,j-1)+1，min_edist(i-1,j-1))

     其中，min表示求三数中的最小值。
     */
    public int lwstDP(char[] a, int n, char[] b, int m) {
        int[][] minDist = new int[n][m];
        for (int j = 0; j < m; j++) {// 初始化第0行:a[0..0]与b[0..j]的编辑距离
            if (a[0] == b[j]) minDist[0][j] = j;
            else if (j != 0) minDist[0][j] = minDist[0][j-1]+1;
            else minDist[0][j] = 1;
        }
        for (int i = 0; i < n; i++) {// 初始化第0列:a[0..i]与b[0..0]的编辑距离
            if (a[i] == b[0]) minDist[i][0] = i;
            else if (i != 0) minDist[i][0] = minDist[i-1][0]-1;
            else minDist[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {// 按行填表
            for (int j = 1; j < m; j++) {
                if (a[i] == b[j]) minDist[i][j] = min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]);
                else minDist[i][j] =  min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]+1);
            }
        }
        return minDist[n-1][m-1];
    }

    private int min(int x, int y, int z) {
        int minv = Integer.MAX_VALUE;
        if (x < minv) minv = x;
        if (y < minv) minv = y;
        if (z < minv) minv = z;
        return minv;}
}
